【Redis】缓存一致性问题解决方案

进程在内存主要分为5个区：
1.代码区 (.text) - 存放函数体的二进制代码
2.文字常量区 (.rodata) - 存放常量字符串
3.静态区 (static) - 存放全局变量、静态变量
4.堆区 (heap) - 开发者手动分配的内存空间，结构类似链表
5.栈去 (stack) - 存放函数参数、局部变量。由编译器自动管理，结构类似栈。

线程

线程是cpu调度的最小单位，一个进程内的线程间资源共享。
线程是由系统内核提供的服务，用户通过系统调用让内核启动线程，内核负责线程的调用和切换。

协程

协程是go自己管理的线程，比系统线程开销更少，速度更快。

Go学习

作者: 杨
时间: 2022-09-08
分类: golang
评论

1.context
2.channel
3.map
4.gmp模型
5.用多个协程交替打印abc
6.多个协程交替打印字符串和数字数组，直到字符串结束。
7.gin.Context
8.协程调度和线程有什么区别
9.sync.Map
10.sync.Mutex
11.sync.RwMutex
12.sync.WaitGroup
13.gc原理

1.context

Context可以控制一组树状结构的goroutine，相比于waitgroup，Context对派生的goroutine比waitgroup有着更强的控制能力。waitgroup适用于确定数量的goroutine，未知数量的goroutine，可采用context控制并发。Context可设置父子关系，父关闭，子也关闭。同时支持延时关闭和超时关闭。

2.channel

channel(通道)是go自带的、且唯一一个并发安全的类型。
一个通道相当于一个FIFO队列。

注意事项

1.向一个已关闭的通道发送操作，会引发panic。
2.试图关闭一个已经关闭的通道也会引发panic。

7.gin

8.协程、线程

9.sync.Map

引入原因

map类型不是并发安全的，并发读写会报fatal error

fatal error: concurrent map read and map write

case:

var testMap  = map[string]string{}
func main() {
   go func() {
      for{
         _ = testMap["bar"]
      }
   }()
   go func() {
      for  {
         testMap["bar"] = "foo"
      }
   }()
   select{}
}

map为何会出现并发异常

go通过flags的hashWriting字段来检测map是否并发异常。
查询操作：
flags.hashWriting > 0，则抛出异常。
写操作：
1.写入前检查一次标记位，通过后打上标记
2.写入完成后再检查标记位，通过后再打上标记


   //各类前置操作
   ....
   if h.flags&amp;hashWriting != 0 {
      //检查是否存在并发
      throw("concurrent map writes")
   }

   //赋值标记位
   h.flags ^= hashWriting
   ....
   //后续操作
  done:
   //完成修改后，再次检查标记位
   if h.flags&hashWriting == 0 {
      throw("concurrent map writes")
   }
   //还原标记位取消hashWriting标记
   h.flags &^= hashWriting

如何解决map并发问题

1.使用sync.RwMutex

type cocurrentMap = struct {
   sync.RWMutex
   m map[string]string
}

func main() {
   var testMap = &cocurrentMap{m:make(map[string]string)}
   //写
   testMap.Lock()
   testMap.m["a"] = "foo"
   testMap.Unlock()
   //读
   testMap.RLock()
   fmt.Println(testMap.m["a"])
   testMap.RUnlock()
}

由于锁开销较大，对并发量有影响，所以推荐使用sync.Map

2.sync.Map

sync.Map的实现

空间换时间思想，同时维护两份数据，readonly&dirty，read用来避免读写冲突。
结构如下:

type Map struct {
   mu Mutex //锁
   read atomic.Value //readOnly
   dirty map[interface{}]*entry //*entry
   misses int
}

type readOnly struct {
   m       map[interface{}]*entry
   amended bool // true if the dirty map contains some key not in m.
}

type entry struct {
   p unsafe.Pointer // *interface{}
}

case:

var m sync.Map
//write
m.Store("test", 1)
m.Store(1, true)

//read
val1, _ := m.Load("test")
val2, _ := m.Load(1)
fmt.Println(val1.(int))
fmt.Println(val2.(bool))

//遍历
m.Range(func(key, value interface{}) bool {
   //....
   return true
})

//删除
m.Delete("test")

//读取或写入
m.LoadOrStore("test", 1)

10.sync.Mutex

11.sync.RwMutex

12.sync.WaitGroup

13.GC原理

转自 https://mp.weixin.qq.com/s/niLk_n9Yp-iyl_RIie3Umw

面试算法总结

作者: 杨
时间: 2022-09-05
分类: 数据结构与算法
评论

最长回文子串

反转链表

x3

括号生成

top K

x2

合并链表

岛屿数量

最大子序列和

x2

有序数组转二叉搜索树

二叉树层序遍历

反转二叉树

是否是有效括号

找出两个有序数组的相同元素

最长公共前缀

x2

整数反转

判断链表是否有环

通道 channel

作者: 杨
时间: 2022-08-30
分类: 默认分类,golang
评论

在Go语言中，‌chan（‌通道）‌是一种用于在goroutines之间进行通信的机制。‌chan可以定义为以下几种类型：‌

不带缓冲的通道：‌这种通道在写入数据时，‌如果接收方没有准备好读取数据，‌写入操作会阻塞，‌直到有接收方准备好读取数据为止。‌不带缓冲的通道确保了数据的同步传输。‌
带缓冲的通道：‌带缓冲的通道允许在通道中存储一定数量的数据，‌每次向通道中写入数据时，‌如果通道未满，‌则写入操作会立即完成；‌当通道已满时，‌写入操作会阻塞，‌直到有数据被读取出来。‌带缓冲的通道提供了一定程度的异步通信能力，‌允许发送方和接收方在不同的时间点进行操作。‌

定义chan时，‌需要指定数据类型，‌只允许这个指定数据类型的变量通过这个通道。‌例如，‌可以定义一个整数类型的通道var intChan chan int，‌或者一个可以存储任意类型的通道var anyChan chan interface{}。‌后者特别有用，‌因为它允许在通道中传递任何类型的值，‌但需要注意的是，‌使用interface{}类型会带来一些类型安全的考虑，‌因为运行时类型检查可能会增加代码的复杂性。‌

通道的操作包括使用<-操作符进行数据的发送或读取，‌以及使用close函数关闭通道。‌关闭通道是一种重要的操作，‌用于指示通道不再发送任何数据，‌这有助于防止内存泄漏和错误地使用已关闭的通道.

【Linux】fork、mmap、页中断

作者: 杨
时间: 2022-06-13
分类: linux
评论

fork原理：写保护中断与写时复制

父进程和子进程不仅可以访问共有的变量，还可以各自修改这个变量，并且这个修改对方都看不见。这其实是 fork 的一种写时复制机制，这一点我们在第 5 节课中模糊提到过，而里面起关键作用的就是写保护中断。下面我们来看看这到底是怎么一回事。

实际上，操作系统为每个进程提供了一个进程管理的结构，在偏理论的书籍里一般会称它为进程控制块（Process Control Block，PCB)。具体到 Linux 系统上，PCB 就是 task_struct 这个结构体。它里面记录了进程的页表基址，打开文件列表、信号、时间片、调度参数和线性空间已经分配的内存区域等等数据。

其中，描述线性空间已分配的内存区域的结构对于内存管理至关重要，我们先来看一下这个结构。在 Linux 源码中，负责这个功能的结构是 vm_area_struct，后面简称 vma。内核将每一段具有相同属性的内存区域当作一个单独的内存对象进行管理。vma 中比较重要的属性我列在下面：


struct vm_area_struct { 
  unsigned long vm_start;      // 区间首地址
  unsigned long vm_end;        // 区间尾地址
    pgprot_t      vm_page_prot;  // 访问控制权限
    unsigned long vm_flags;      // 标志位
    struct file * vm_file;       // 被映射的文件
    unsigned long vm_pgoff;      // 文件中的偏移量
  ...
}

在操作系统内核里，fork 的第一个动作是把 PCB 复制一份，但类似于物理页等进程资源不会被复制。这样的话，父进程与子进程的代码段、数据段、堆和栈都是相同的，这是因为它们拥有相同的页表，自然也有相同的虚拟空间布局和对物理内存的映射。如果父进程在 fork 子进程之前创建了一个变量，打开了一个文件，那么父子进程都能看到这个变量和文件。

fork 的第二个动作是复制页表和 PCB 中的 vma 数组，并把所有当前正常状态的数据段、堆和栈空间的虚拟内存页，设置为不可写，然后把已经映射的物理页面的引用计数加 1。这一步只需要复制页表和修改 PTE 中的写权限位可以了，并不会真的为子进程的所有内存空间分配物理页面，修改映射，所以它的效率是非常高的。这时，父子进程的页表的情况如下图所示：
父子进程页表情况图.png

在上图中，物理页括号中的数字代表该页被多少个进程所引用。Linux 中用于管理物理页面，和维护物理页的引用计数的结构是 mem_map 和 page struct。

这两个动作执行完后，fork 调用就结束了。此时，由于有父进程和子进程两个 PCB，操作系统就会把两个进程都加入到调度队列中。当父进程得到执行，它的 IP 寄存器还是指向 fork 调用中，所以它会从这个调用中返回，只不过返回值是子进程的 PID。当子进程得到执行时，它的 IP 寄存器也是停在 fork 调用中，它从这个调用中返回，其返回值是 0。

接下来，就是写保护中断要发挥作用的地方了。不管是父进程还是子进程，它们接下来都有可能发生写操作，但我们知道在 fork 的第二步操作中，已经将所有原来可写的地方都变成不可写了，所以这时必然会发生写保护中断。

我们刚才说，Linux 系统的页中断的入口地址是 do_page_fault，在这个函数里，它会继续判断中断的类型。由于发生中断的虚拟地址在 vma 中是可写的，在 PTE 中却是只读的，可以断定这是一次写保护中断。这时候，内核就会转而调用 do_wp_page 来处理这次中断，wp 是 write protection 的缩写。

在 do_wp_page 中，系统会首先判断发生中断的虚拟地址所对应的物理地址的引用计数，如果大于 1，就说明现在存在多个进程共享这一块物理页面，那么它就需要为发生中断的进程再分配一个物理页面，把老的页面内容拷贝进这个新的物理页，最后把发生中断的虚拟地址映射到新的物理页。这就完成了一次写时复制 (Copy On Write， COW）。具体过程如下图所示：
写时复制过程.png
在上图中，当子进程发生写保护中断后，系统就会为它分配新的物理页，然后复制页面，再修改页表映射。这时老的物理页的引用计数就变为 1，同时子进程中的 PTE 的权限也从只读变为读写。

当父进程再访问到这个地址时，也会触发一次写保护中断，这时系统发现物理页的引用计数为 1，那就只要把父进程 PTE 中的权限，简单地从只读变为读写就可以了。这个过程比较简单，我就不画图了，你可以自己思考一下。

杨 发布的文章

主从第一次同步

进程

内存管理

线程

协程